package com.shuo.dsa.leetcode;

import com.shuo.dsa.model.ListNode;

/**
 * 插入排序来排序链表
 *      思路: new个哨兵节点作为新链表的虚节点
 */
public class SortInsertList {
    public ListNode insertionSortList(ListNode head) {
        ListNode temp = head;
        ListNode next;
        ListNode sentinel = new ListNode(Integer.MIN_VALUE);
        while (temp != null) {
            next = temp.next;
            temp.next = null;
            insertAfter(sentinel, temp);
            temp = next;
        }
        return sentinel.next;
    }

    private void insertAfter(ListNode list, ListNode newNode) {
        ListNode temp = list;
        ListNode pre = temp;
        while (temp != null) {
            if (temp.val > newNode.val) {
                pre.next = newNode;
                newNode.next = temp;
                return;
            }
            pre = temp;
            temp = temp.next;
        }
        pre.next = newNode;
        newNode.next = null;
    }
}
